package com.nulldev.util.math;

import java.math.BigInteger;
import java.util.AbstractList;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.TimeUnit;

import com.nulldev.util.math.u.FastMath;
import com.nulldev.util.math.u.UnivariateFunction;
import com.nulldev.util.other.ArrayUtils;
import com.nulldev.util.other.RandomUtils.nSecureRandom;

public class MathUtil {
	
	public static class TimeToSeconds {
	    // given: mm:ss or hh:mm:ss or hhh:mm:ss, return number of seconds.
	    // bad input throws NumberFormatException.
	    // bad includes:  "", null, :50, 5:-4
	    public static long parseTime(String str) throws NumberFormatException {
	        if (str == null)
	            throw new NumberFormatException("parseTimeString null str");
	        if (str.isEmpty())
	            throw new NumberFormatException("parseTimeString empty str");

	        int h = 0;
	        int m, s;
	        String units[] = str.split(":");
	        assert (units.length == 2 || units.length == 3);
	        switch (units.length) {
	            case 2:
	                // mm:ss
	                m = Integer.parseInt(units[0]);
	                s = Integer.parseInt(units[1]);
	                break;

	            case 3:
	                // hh:mm:ss
	                h = Integer.parseInt(units[0]);
	                m = Integer.parseInt(units[1]);
	                s = Integer.parseInt(units[2]);
	                break;

	            default:
	                throw new NumberFormatException("parseTimeString failed:" + str);
	        }
	        if (m<0 || m>60 || s<0 || s>60 || h<0)
	            throw new NumberFormatException("parseTimeString range error:" + str);
	        return h * 3600 + m * 60 + s;
	    }

	    // given time string (hours:minutes:seconds, or mm:ss, return number of seconds.
	    public static long parseTimeStringToSeconds(String str) {
	        try {
	            return parseTime(str);
	        } catch (NumberFormatException nfe) {
	            return 0;
	        }
	    }

	}
	
	public static class lNumberUtils {
		
		public static String add(String addend1, String addend2) {
		    StringBuilder buf = new StringBuilder();
		    for ( int i1 = addend1.length() - 1, i2 = addend2.length() - 1, carry = 0;
		          i1 >= 0 || i2 >= 0 || carry != 0;
		          i1--, i2-- ) {
		        int digit1 = i1 < 0 ? 0 :
		                     Integer.parseInt(Character.toString(addend1.charAt(i1)));
		        int digit2 = i2 < 0 ? 0 :
		                     Integer.parseInt(Character.toString(addend2.charAt(i2)));

		        int digit = digit1 + digit2 + carry;
		        if (digit > 9) {
		            carry = 1;
		            digit -= 10;
		        } else {
		            carry = 0;
		        }

		        buf.append(digit);
		    }
		    return buf.reverse().toString();
		}
		
	}

	private static char[] hexDigits = new char[] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' };
	
	public static int randInt(int min, int max) {
	    final Random rand = new Random();
	    int randomNum = rand.nextInt((max - min) + 1) + min;
	    return prevRand = randomNum;
	}
	
	public static int secureRandInt(final int min, final int max) {
		final nSecureRandom nsr = new nSecureRandom();
		return nsr.nextInt((max - min) + 1) + min;
	}
	
	public static float randFloat(float min, float max) {
	    final Random rand = new Random();
	    float randomNum = rand.nextFloat() * (max - min) + min;
	    return randomNum;
	}
	
	static long nextLong(Random rng, long n) {
		   // error checking and 2^x checking removed for simplicity.
		   long bits, val;
		   do {
		      bits = (rng.nextLong() << 1) >>> 1;
		      val = bits % n;
		   } while (bits-val+(n-1) < 0L);
		   return val;
		}
	
	public static long randLong(final long min, final long max)
	{
	    final Random rand = new Random();
	    final long randomNum = nextLong(rand, (max - min) + 1) + min;
	    return randomNum;
	}
	
	public static double averageD(final List<Double> x) {
	    double sum = 0;
	    for (double aX : x) sum += aX;
	    return (sum / x.size());
	}
	
	public static int averageI(final List<Integer> x) {
	    double sum = 0;
	    for (double aX : x) sum += aX;
	    return (int) (sum / x.size());
	}
	
	public static float averageF(final List<Float> x) {
	    double sum = 0;
	    for (double aX : x) sum += aX;
	    return (float) (sum / x.size());
	}

	public static String formatSeconds(int timeInSeconds)
	{
	    int hours = timeInSeconds / 3600;
	    int secondsLeft = timeInSeconds - hours * 3600;
	    int minutes = secondsLeft / 60;
	    int seconds = secondsLeft - minutes * 60;

	    String formattedTime = "";
	    if (hours < 10)
	        formattedTime += "0";
	    formattedTime += hours + ":";

	    if (minutes < 10)
	        formattedTime += "0";
	    formattedTime += minutes + ":";

	    if (seconds < 10)
	        formattedTime += "0";
	    formattedTime += seconds ;

	    return formattedTime;
	}
	
	public static String formatSecondsL(long timeInSecondsLong)
	{
		long timeInSeconds = Long.parseLong(String.valueOf(timeInSecondsLong).replace("-", ""));
		
		long hours = timeInSeconds / 3600;
		long secondsLeft = timeInSeconds - hours * 3600;
		long minutes = secondsLeft / 60;
		long seconds = secondsLeft - minutes * 60;

	    String formattedTime = "";
	    if (hours < 10)
	        formattedTime += "0";
	    formattedTime += hours + ":";

	    if (minutes < 10)
	        formattedTime += "0";
	    formattedTime += minutes + ":";

	    if (seconds < 10)
	        formattedTime += "0";
	    formattedTime += seconds ;

	    return formattedTime;
	}

	public static Object handleMS(final long ms) {
		if (ms <= 0) {
			return "<1";
		}else {
			return ms;
		}
	}

    public static String toHexadecimal(final byte[] message) {
        if (message == null) {
            return null;
        }
        final StringBuffer buffer = new StringBuffer();
        for (int i = 0; i < message.length; ++i) {
            final int curByte = message[i] & 0xFF;
            buffer.append(hexDigits[curByte >> 4]);
            buffer.append(hexDigits[curByte & 0xF]);
        }
        return buffer.toString();
    }

    public static byte[] fromHexadecimal(final String message) {
        if (message == null) {
            return null;
        }
        if (message.length() % 2 != 0) {
            throw new RuntimeException("Not possible.");
        }
        try {
            final byte[] result = new byte[message.length() / 2];
            for (int i = 0; i < message.length(); i += 2) {
                final int first = Integer.parseInt("" + message.charAt(i), 16);
                final int second = Integer.parseInt("" + message.charAt(i + 1), 16);
                result[i / 2] = (byte)(0 + ((first & 0xFF) << 4) + (second & 0xFF));
            }
            return result;
        }
        catch (Exception e) {
        	throw new RuntimeException("Not possible.");
        }
    }

    public static int nextRandomInt() {
        return (int) (Math.random() * 2.147483647E9);
    }

	public static int safeLongToInt(long l) {
	    if (l < Integer.MIN_VALUE || l > Integer.MAX_VALUE) {
	        throw new IllegalArgumentException
	            (l + " cannot be cast to int without changing its value.");
	    }
	    return (int) l;
	}

	public static float clamp(final float min, final float max, final float val) {
		if (val < min) {
			return min;
		}else if (val > max) {
			return max;
		}else {
			return val;
		}
	}

	public static double clamp(final double min, final double max, final double val) {
		if (val < min) {
			return min;
		}else if (val > max) {
			return max;
		}else {
			return val;
		}
	}
	
	public static int clamp(final int min, final int max, final int val) {
		if (val < min) {
			return min;
		}else if (val > max) {
			return max;
		}else {
			return val;
		}
	}

	public static boolean stringBetweenList(final String[] data, final int index, final int min, final int max) {
		try {
			return Integer.parseInt(data[index]) > min && Integer.parseInt(data[index]) < max;
		}catch (Exception e) {
			return false;
		}
	}
	
	public static boolean stringBetweenListRC(final String[] data, final int index, final int min, final int max) {
		try {
			return Integer.parseInt(data[index].replaceAll("[^\\d]", "" )) > min && Integer.parseInt(data[index].replaceAll("[^\\d]", "" )) < max;
		}catch (Exception e) {
			return false;
		}
	}

	public static boolean stringBetween(final String data, final int min, final int max) {
		try {
			return Integer.parseInt(data) > min && Integer.parseInt(data) < max;
		}catch (Exception e) {
			return false;
		}
	}

	public static int safeParseList(final String[] data, final int index, final int fallback) {
		try {
			return Integer.parseInt(data[index]);
		}catch (Exception e) {
			return fallback;
		}
	}

	public static int safeParseI(final String text, final int fallback) {
		if (text == null) {
			return fallback;
		}
		try {
			return Integer.parseInt(text);
		}catch (Exception e) {
			return fallback;
		}
	}
	
	public static double safeParseD(final String text, final double fallback) {
		try {
			return Double.parseDouble(text);
		}catch (Exception e) {
			return fallback;
		}
	}
	
	public static long safeParseL(final String text, final long fallback) {
		try {
			return Long.parseLong(text);
		}catch (Exception e) {
			return fallback;
		}
	}
	
	public static float safeParseF(final String text, final float fallback) {
		try {
			return Float.parseFloat(text);
		}catch (Exception e) {
			return fallback;
		}
	}

	public static boolean between(final int value, final int min, final int max) {
		if (value >= min && value <= max) {
			return true;
		} else {
			return false;
		}
	}
	
	public static boolean between(final double value, final double min, final double max) {
		if (value >= min && value <= max) {
			return true;
		} else {
			return false;
		}
	}
	
	public static boolean between(final long value, final long min, final long max) {
		if (value >= min && value <= max) {
			return true;
		} else {
			return false;
		}
	}
	
	public static boolean isBetween(int a, int b, int c) {
	    return b >= a ? c >= a && c <= b : c >= b && c <= a;
	}

	public static String timeZero(final int hours) {
		if (hours < 10 && hours > -10) {
			return "0" + hours;
		}else {
			return String.valueOf(hours);
		}
	}

	public static double minClamp(final double min, final double value) {
		if (value < min) {
			return min;
		}
		return value;
	}
	
	public static int minClamp(final int min, final int value) {
		if (value < min) {
			return min;
		}
		return value;
	}
	
	public static int minClampI(final int min, final int value) {
		if (value < min) {
			return min;
		}
		return value;
	}

	public static long minClampL(final long min, final long value) {
		if (value < min) {
			return min;
		}
		return value;
	}
	
	public static Integer[] shareOverString(final String mul, final String str) {
		final ArrayList<Integer> out = new ArrayList<Integer>();
		final double toShare = (double) divNoZero(mul.length(), str.length());
		double currentVar = toShare;
		for (int i = 0; i < str.length() - 1; i++) {
			//System.out.println("currentVar: " + (int) currentVar);
			out.add((int) mul.charAt((int) currentVar));
			currentVar += toShare;
		}
		return ArrayUtils.arrayListToArray(out);
	}

	public static double divNoZero(int i1, int i2) {
		if (i2 == 0) {
			i2 = 1;
		}
		if (i1 == 0) {
			i1 = 1;
		}
		return i1 / i2;
	}
	
	/**
	 * @param begin inclusive
	 * @param end exclusive
	 * @return list of integers from begin to end
	 */
	public static List<Integer> range(final int begin, final int end) {
	    return new AbstractList<Integer>() {
	            @Override
	            public Integer get(int index) {
	                return begin + index;
	            }

	            @Override
	            public int size() {
	                return end - begin;
	            }
	        };
	}

	public static boolean isDiv(final int iteration, final int val) {
		return iteration % val == 0;
	}

	public static boolean isNumeric(final String str) {
	  return str.matches("-?\\d+(\\.\\d+)?");  //match a number with optional '-' and decimal.
	}

	public static String toHex(final int num) {
		return Integer.toHexString(num);
	}

	private static int prevRand = -1;
	public static int prevRand() {
		if (prevRand == -1) {
			prevRand = MathUtil.randInt(0, 10000000);
			return prevRand;
		}else {
			return prevRand;
		}
	}

	public static boolean isInTimesTable(final int toCheck, final int timesTable, final int maxToCheck) {
		final ArrayList<Integer> vals = new ArrayList<Integer>();
		for (int i = 0; i < maxToCheck + 1; i++) {
			vals.add(i * timesTable);
		}
		for (Integer i : vals) {
			if (i == toCheck) {
				return true;
			}
		}
		return false;
	}

	public static Integer[] getVals(final String object) {
		if (object == null) {
			throw new RuntimeException("object == null!! | getVals() -> MathUtil.class");
		}
		final ArrayList<Integer> out = new ArrayList<Integer>();
		for (final char c : object.toCharArray()) {
			out.add((int) c);
		}
		return ArrayUtils.arrayListToArray(out);
	}

	public static Long[] getValsL(final String object) {
		final ArrayList<Long> out = new ArrayList<Long>();
		for (final char c : object.toCharArray()) {
			out.add((long) c);
		}
		return ArrayUtils.arrayListToArray(out);
	}

	public static Long[] getValsLi(final String object) {
		final ArrayList<Long> cx = new ArrayList<Long>();
		for (final String s : object.split(",")) {
			cx.add(Long.parseLong(s));
		}
		return ArrayUtils.arrayListToArray(cx);
	}
	
	public static BigInteger[] getValsB(final String object) {
		final ArrayList<BigInteger> out = new ArrayList<BigInteger>();
		for (final char c : object.toCharArray()) {
			out.add(new BigInteger(String.valueOf((int) c)));
		}
		return ArrayUtils.arrayListToArray(out);
	}

	public static BigInteger[] getValsBi(final String object) {
		final ArrayList<BigInteger> cx = new ArrayList<BigInteger>();
		for (final String s : object.split(",")) {
			cx.add(new BigInteger(s));
		}
		return ArrayUtils.arrayListToArray(cx);
	}

    public static int hash(final double value) {
        return new Double(value).hashCode();
    }

    public static boolean equals(final double x, final double y) {
        return new Double(x).equals(new Double(y));
    }

    public static boolean isPowerOfTwo(final long n) {
        return n > 0L && (n & n - 1L) == 0x0L;
    }

    public static double[] sample(final UnivariateFunction f, final double min, final double max, final int n) {
        if (n <= 0) {
            throw new RuntimeException("n <= 0");
        }
        if (min >= max) {
            throw new RuntimeException("min > max");
        }
        final double[] s = new double[n];
        final double h = (max - min) / n;
        for (int i = 0; i < n; ++i) {
            s[i] = f.value(min + i * h);
        }
        return s;
    }

    public static int[] copyOf(final int[] source) {
        return copyOf(source, source.length);
    }
    
    public static double[] copyOf(final double[] source) {
        return copyOf(source, source.length);
    }
    
    public static int[] copyOf(final int[] source, final int len) {
        final int[] output = new int[len];
        System.arraycopy(source, 0, output, 0, FastMath.min(len, source.length));
        return output;
    }
    
    public static double[] copyOf(final double[] source, final int len) {
        final double[] output = new double[len];
        System.arraycopy(source, 0, output, 0, FastMath.min(len, source.length));
        return output;
    }

	public static long toSeconds(long ms) {
		return TimeUnit.MILLISECONDS.toSeconds(ms);
	}

	public static byte[] randomBytes(byte[] data) {
		final Random r = new Random();
		r.nextBytes(data);
		return data;
	}

	public static BigInteger hashString(final String pass) {
		BigInteger out = new BigInteger("1");
		for (final char c : pass.toCharArray()) {
			final int x = (int) (c);
			out = out.multiply(new BigInteger(String.valueOf(x)));
		}
		return out;
	}

	public static int clampLong(final long length) {
		if (length > Integer.MAX_VALUE) {
			return Integer.MAX_VALUE;
		}else if (length < Integer.MIN_VALUE) {
			return Integer.MIN_VALUE;
		}
		return (int) length;
	}

	public static long fromFormat(final String text) {
		long factor = 1;
		final boolean expanded = text.endsWith("B") || text.endsWith("M") || text.endsWith("K");
		if (text.endsWith("B")) {
			factor = (long) 1e9;
		}else if (text.endsWith("M")) {
			factor = (long) 1e6;
		}else if (text.endsWith("K")) {
			factor = (long) 1e3;
		}
		final String toS = text.substring(0, text.length() - 1);
		String x0 = (expanded ? toS : text).replaceAll(",", "");
		double l = MathUtil.safeParseD(x0, -1);
		if (l != -1) {
			l *= factor;
		}
		return (long) l;
	}
	
	private static final int[] logTab = new int[] { 0, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4,
            4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
            5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
            6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7,
            7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
            7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
            7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
            7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7 
    };

	public static int log2(int v) {
        int n = 0;
        if ((v & 0xffff0000) != 0) {
            v >>= 16;
            n += 16;
        }
        if ((v & 0xff00) != 0) {
            v >>= 8;
            n += 8;
        }
        n += logTab[v];

        return n;	
	}
	
	public static final int abs(int val) {
        int sign = (val >> 31);
        return (val ^ sign) - sign;
    }

    public static final int golomb(int signedLevel) {
        if (signedLevel == 0)
            return 0;
        return (abs(signedLevel) << 1) - (~signedLevel >>> 31);
    }
    
    public static final int clip(int val, int from, int to) {
        return val < from ? from : (val > to ? to : val);
    }

    public static final int clipMax(int val, int max) {
        return val < max ? val : max;
    }
    
    public static int gcd(int a, int b) {
        if (b != 0)
            return gcd(b, a % b);
        else
            return a;
    }

    public static long gcdLong(long a, long b) {
        if (b != 0)
            return gcdLong(b, a % b);
        else
            return a;
    }
    
    public static void putLong(long value, byte[] array, int offset) {
        array[offset]   = (byte)(0xff & (value >> 56));
        array[offset+1] = (byte)(0xff & (value >> 48));
        array[offset+2] = (byte)(0xff & (value >> 40));
        array[offset+3] = (byte)(0xff & (value >> 32));
        array[offset+4] = (byte)(0xff & (value >> 24));
        array[offset+5] = (byte)(0xff & (value >> 16));
        array[offset+6] = (byte)(0xff & (value >> 8));
        array[offset+7] = (byte)(0xff & value);
    }

    public static long getLong(byte[] array, int offset) {
        return
          ((long)(array[offset]   & 0xff) << 56) |
          ((long)(array[offset+1] & 0xff) << 48) |
          ((long)(array[offset+2] & 0xff) << 40) |
          ((long)(array[offset+3] & 0xff) << 32) |
          ((long)(array[offset+4] & 0xff) << 24) |
          ((long)(array[offset+5] & 0xff) << 16) |
          ((long)(array[offset+6] & 0xff) << 8) | 
          ((long)(array[offset+7] & 0xff));
    }
    
    public static void putInt(int value, byte[] array, int offset) {
        array[offset]   = (byte)(0xff & (value >> 24));
        array[offset+1] = (byte)(0xff & (value >> 16));
        array[offset+2] = (byte)(0xff & (value >> 8));
        array[offset+3] = (byte)(0xff & value);
    }

    public static int getInt(byte[] array, int offset) {
        return
          ((array[offset]   & 0xff) << 24) |
          ((array[offset+1] & 0xff) << 16) |
          ((array[offset+2] & 0xff) << 8) |
           (array[offset+3] & 0xff);
    }

	public static int nonNegative(final int val) {
		return safeParseI(String.valueOf(val).substring(1), val);
	}

	public static int gen_rand_id() {
		return randInt(Integer.MIN_VALUE, Integer.MAX_VALUE);
	}
}
